package 动态规划;

public class No474一和零 {

    /**
     * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
     * 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
     * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
     *
     * 示例 1：
     * 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
     * 输出：4
     * 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
     * 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，
     * 因为它含 4 个 1 ，大于 n 的值 3 。
     * 示例 2：
     * 输入：strs = ["10", "0", "1"], m = 1, n = 1
     * 输出：2
     * 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
     */

    /**
     * 对每个元素进行遍历,然后让每个元素对好 dp数组
     * f(m,n)=max(f(m,n),f(m-[m],n-[n])+1);
     * 二维倒序版
     * 底下有三维正序版
     */
    public int findMaxForm(String[] strs, int m, int n) {

        int[][] dp=new int[m+1][n+1];

        for (int i = 0; i < strs.length; i++) {
            int[] countMN = getCountMN(strs[i]);
            /**
             * 前序影响后序,而后序不应该被前序影响
             */
            for (int j = m; j >= countMN[0]; j--) {
                for (int k = n; k >= countMN[1]; k--) {

                    dp[j][k]=Math.max(dp[j][k],dp[j-countMN[0]][k-countMN[1]]+1);

                }
            }
        }

        return dp[m][n];
    }

    public int[] getCountMN(String str){
        int m=0;
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i)=='0'){
                m++;
            }
        }
        return new int[]{m,str.length()-m};
    }

    public int findMaxForm3D(String[] strs, int m, int n){

        int[][][] dp=new int[strs.length][m+1][n+1];

        int[] countMNFirst=getCountMN(strs[0]);
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if(j>=countMNFirst[0]&&k>=countMNFirst[1]) {
                    dp[0][j][k] = 1;
                }
            }
        }

        for (int i = 1; i < strs.length; i++) {
            int[] countMN=getCountMN(strs[i]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    //一定要先把上一行的抄下来先
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j>=countMN[0]&&k>=countMN[1]){
                        dp[i][j][k]=Math.max(dp[i-1][j][k],dp[i-1][j-countMN[0]][k-countMN[1]]+1);
                    }

                }
            }
        }

        return dp[strs.length-1][m][n];

    }

    public static void main(String[] args) {
        No474一和零 n=new No474一和零();
        String[] arr={"10", "0001", "111001", "1", "0"};
        int result = n.findMaxForm3D(arr, 5, 3);
        System.out.println(result);
    }

}
